1. Field of the Invention
The invention relates to packet processing apparatus, to methods of reconfiguring a packet processor, and to methods of using a packet processor.
2. Background Art
It is known to transmit data in packets, each packet having header information as part of the packet, for use in processing the packet. The location and meaning of the header information within each packet is defined by a protocol. Most packet data transmission networks use multiple layers of protocols, in a hierarchy, according to the well known ISO model. Starting with the raw data from a top level application, each protocol adds its own header information to that added previously by preceding (higher) protocols. In the course of transmission through the network, the packet may pass through and be routed, forwarded switched or processed according to information stored in various parts of the packet header, depending on which level of the various levels of protocols, is being used.
Conventionally, in a router or switch operating according to a given one of the protocols, for each incoming packet, particular bits in the header relating to that given protocol are examined. The packet would be routed using those bits and passed to a chosen output port. Dedicated hardware is often used for speed of operation.
New types of protocol processing using different parts of header or payload information with different meanings, are always being proposed, at all different layers, to meet new requirements for e.g. quality of service, billing functions, error handling, grouping of packets, prioritizing, and so on. However, development of appropriate hardware is time consuming, even when groups of programmable logic chips are used, for a number of reasons. Connections between such chips must be defined and fixed, and changes made to the relatively complex logic which is often involved, will often have consequences to other parts of the logic, which are difficult to manage.
Software simulations and verifications of hardware designs can be carried out, but often do not reveal all the problems of a real hardware implementation.
Programmable chips for switching packets of particular protocols are known, e.g. ethernet switching chips, and protocol-specific dedicated router chips. Such router chips can extract destination information from a packet using hardcoded logic to achieve higher speed or throughput. They use a routing table whose entries can programmed from an external host.
A chipset produced by Obtek provides multiprotocol packet routing. A programmable filter examines the contents of each incoming packet to derive the buried protocols and retrieve source and destination addresses. The filter passes a packet descriptor to a routing systems control chip which manages memory allocation, input and output queues.
This filter is programmable using a proprietary language, a rule-based language which enables a programmer to define actions to be taken according to recognition of bits in a packet. As the filter""s active structure parses and processes the unknown incoming packet, it is capable of activating other processors (including a host) or special hardware (for very high performance) to perform concurrent and supporting tasks.
It is an object of the invention to provide improved methods and apparatus.
According to a first aspect of the invention there is provided a packet processing apparatus comprising:
a programmable hardware discriminator for receiving incoming packets, and selecting bits from any part of the incoming packets;
a decision table for storing information relating to how the packets are to be processed;
programmable hardware searching logic coupled to the decision table and to the discriminator for accessing the information in the table according to the selected bits; and
a packet handler coupled to the searching logic, for processing the packets according to the result of the access.
Advantages include the following:
a) Providing programmable table searching logic means that the search algorithm and any corresponding table maintenance functions can be altered without necessarily altering the table contents, or the bit selection hardware. This separation of these functions can make it easier to develop and refine applications using new protocol components, since changes to algorithms can be made more directly, at a lower level. It may enable applications to be developed to run faster, or use memory more efficiently for example. This was not possible in previous arrangements in which it was only possible to define the overall outputs of such algorithms for given states of the bits selected from the packet, without being able to define how the selected bits were processed, or how a table of all the possible outputs is searched.
b) Since many networking processing tasks can be broken down into bit selection and table searching, this generic type of arrangement will suit a wide variety of applications.
c) Having the bit selection function programmable, and able to select bits from any part of the incoming packets enables a wider range of operations using different protocols to be handled. This also makes it easier to interface with different input line interfaces, and enables subsequent processing to be streamlined, if all the necessary information in the packet can be extracted in one step.
d) Providing the table searching logic in hardware enables the speed of operation to be faster than equivalent software, and makes it easier for the developer to resolve timing issues in the design.
e) Developing logic directly in hardware can reduce the effort needed to convert a working prototype into a product ready for use in the field, and thus reduce the all important time to market for a product. The arrangement could be used in networks which are designed to be reconfigurable in operation, e.g. active networks which may be reconfigured to suit traffic conditions.
f) Having a programmable search algorithm enables the algorithm to be tailored to reduce search times, and improve throughput, for example by using the minimum number of bits or columns in the table necessary for searching, according to the application.
g) Having an explicit table can make it easier to maintain the contents of the table if it can be accessed directly. This is in contrast to previous arrangements having an implicit table not accessible directly, but defined by mappings of output for a given state of bits selected from the packet. If there are many such mappings having the same output, then any change in that one output would require changing all the mappings which mention that output. Having direct access to the table enables one table entry to be changed which may be simpler and quicker than changing multiple mappings in such a case.
Preferably the apparatus further comprises at least one packet output port, and the packet handler comprises a programmable hardware interpreting logic coupled to the packet output port, for interpreting the result of the access, to control the packet output port.
An advantage of providing a programmable interpreting logic is that the reaction to the result of the table search can be separately programmed, without necessarily altering other elements.
Preferably the interpreting logic is arranged to react to both a match and a mismatch result.
An advantage of being able to program action on a mismatch is that it broadens the range of applications to cover for example those in which a mismatch result can be used to alter the table, or to broadcast a packet. This is significant for following the xe2x80x9croute once, switch manyxe2x80x9d principle, which means where a packet is received, if the table does not include its destination, it may be routed by for example a host CPU based routing algorithm, or by broadcasting to neighbouring nodes, but thereafter, the table learns the destination, and the remaining packets can be switched without the lengthy delay of using the CPU, or the inefficiency inherent in broadcasting.
Preferably the programmable hardware searching logic being arranged to be reprogrammable while in operation without interrupting the accessing of the information in the table.
One advantage is that changes or upgrades can be made more easily, without needing to reinitialize the system. In field applications, maintenance or upgrades become easier, since service can be maintained without interruption. Furthermore, it makes the apparatus more suitable for use as an active node in an active network, since the node can be reconfigured more easily with less likelihood of disrupting service.
Preferably, the apparatus further comprises a table maintenance means coupled to the decision table to modify the decision table according to parameters derived from the incoming packets.
An advantage of being able to modify the table from incoming packets is that the apparatus can better cover applications in which the table must be self learning. This feature is also significant for following the xe2x80x9croute once, switch manyxe2x80x9d principle. This applies whether the table maintenance means receives the derived parameters from the host CPU or whether it receives the packets and derives the parameters itself.
Preferably the table maintenance means comprises programmable hardware logic for deriving the parameters from the incoming packet. An advantage of this, is that such modifications can be made more quickly than if the host CPU makes the derivation.
Preferably the apparatus further comprises at least one packet output port, and the packet handler comprises programmable hardware interpreting logic coupled to the packet output port, for interpreting the result of the access, to control the packet output port, the table maintenance means being coupled to the interpreting logic, and being arranged to modify the decision table on the basis of an output of the interpreting logic. An advantage of such an arrangement is that self learning of the table resulting for example from null search results, can be carried out more quickly than if the host CPU needs to be invoked.
Preferably the apparatus further comprises a host processor, the table maintenance means being coupled to the host processor and being arranged to modify the decision table on the basis of an output of the host processor. An advantage is the greater flexibility enabled by having the host CPU control the operation.
Preferably the discriminator further comprises a comparator for receiving the incoming packets, and comparing at least a portion of each packet with predetermined data, to identify particular types of packet from the incoming packets, the table maintenance means being coupled to the comparator and being arranged to modify the decision table on the basis of an output of the comparator. An advantage of being able to modify the table upon identification of a predetermined packet is that protocols which include packets carrying routing information for example, can be handled more quickly than if they must be passed to the host CPU.
Preferably the discriminator further comprises a comparator for receiving the incoming packets, and comparing at least a portion of each packet with predetermined data, to identify particular types of packet from the incoming packets, and process the packet according to its type. An advantage is that packets destined for the host CPU for example, can be routed there directly without the delay and additional processing overhead of a table search.
Preferably the programmable hardware searching logic is arranged to access concurrently the information in the table relating to a plurality of the incoming packets. An advantage arising is an increase in throughput for what may otherwise be a bottleneck, particularly if the table is large.
Preferably the packet handler further comprises a packet switching fabric.
Preferably the apparatus is part of a programmable packet filter.
Preferably the apparatus is part of a programmable node in an active network.
According to a further aspect of the invention there is provided a packet processing apparatus comprising:
a programmable hardware discriminator for receiving incoming packets, and selecting bits from any part of the incoming packets;
a programmable hardware table processor coupled to the discriminator and comprising a decision table containing information relating to how the packets are to be processed, the processor further comprising hardware searching logic for accessing the information in the table according to the selected bits;
a packet handler coupled to the table processor, for processing the packets according to the accessed information; and
and a means to modify the decision table according to parameters derived from the incoming packets. According to a further aspect of the invention there is provided a method of reconfiguring a packet processor, the packet processor comprising:
a programmable hardware discriminator for receiving incoming packets, and selecting bits from any part of the incoming packets;
a decision table containing information relating to how the packets are to be processed; and
programmable hardware searching logic coupled to the decision table and to the discriminator for accessing the information in the table according to the selected bits; the method comprising the steps of:
determining a column structure for the decision table;
determining which bits to select from each packet;
determining a correspondence between the selected bits and the columns of the table;
determining which bits are to be used in the search;
deriving a new configuration for the discriminator on the basis of the determination of which bits to select;
deriving a new configuration for the searching logic on the basis of the column structure, which bits are to be used in the search, and the correspondence; and
loading the new configurations into the searching logic, and the discriminator respectively.
According to a further aspect of the invention there is provided a method of reconfiguring a packet processor, the packet processor comprising:
a programmable hardware discriminator for receiving incoming packets, and selecting bits from any part of the incoming packets;
a decision table containing information relating to how the packets are to be processed; and
programmable hardware searching logic coupled to the decision table and to the discriminator for accessing the information in the table according to the selected bits; the method comprising the steps of:
receiving incoming packets, and using the packet processor to recognise an incoming packet which indicates that the processor should be reconfigured;
deriving from the incoming packet new configurations for at least one of the discriminator, the searching logic, and the decision table.
According to a further aspect of the invention there is provided a method of using the above mentioned packet processor apparatus.
Any of the preferred features may be combined, and combined with any aspect of the invention, as would be apparent to a person skilled in the art. Other advantages will be apparent to a person skilled in the art, particularly in relation to prior art other than that mentioned above.
To show, by way of example, how to put the invention into practice, embodiments will now be described in more detail, with reference to the accompanying drawings.